package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description leetcode 214. 最短回文串
 * @date 2025/10/21 9:55
 */
public class E214 {

    /**
     * 中心扩展法
     *
     * @param s 字符串
     * @return 最短回文
     */
    public String shortestPalindrome(String s) {
        char[] source = s.toCharArray();
        int median = (source.length - 1) >> 1;
        // 中心一个字符的情况
        String one = handle(source, median, median);
        // 中心两个字符的情况
        String two = handle(source, median, median + 1);
        if (two.length() < one.length() && !two.isEmpty()) return two;
        return one;
    }

    /**
     * 中心扩展
     *
     * @param source  字符串
     * @param medianL 中心左边字符索引
     * @param medianR 中心右边字符索引
     * @return 最短回文
     */
    private String handle(char[] source, int medianL, int medianR) {
        while (medianL >= 0) {
            int left = medianL, right = medianR;
            while (left >= 0 && right < source.length && source[left] == source[right]) {
                left--;
                right++;
            }
            if (left != -1) {
                medianL--;
                medianR--;
                continue;
            }
            StringBuilder builder = new StringBuilder();
            for (int i = source.length - 1; i >= right; i--) {
                builder.append(source[i]);
            }
            builder.append(new String(source));
            return builder.toString();
        }
        return "";
    }
}
